//
// Description: 867. 分解质因数
// Created by Loading on 2022/5/24.
//

#include <bits/stdc++.h>

using namespace std;

void divide(int n) {
    // n 最多只存在一个大于 sqrt(n) 的质因子，如果有两个，则两者乘积大于 n，矛盾
    // 条件只需要写成 i <= n / i 即可
    /*
     * 时间复杂度：O(logn) ~ O(sqrt(n))
     * 不推荐写法：
     * 1、i <= sqrt(n)，每次循环都会计算sqrt(n)，效率低；
     * 2、i * i <= n，当 n 较大时，i * i 很容易越界
     */
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                ++cnt;
            }
            if (cnt > 0) {
                cout << i << ' ' << cnt << endl;
            }
        }
    }
    // 处理这个大于 sqrt(n) 的质因子
    if (n > 1) {
        cout << n << ' ' << 1 << endl;
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}